package com.yun.algorithm.string;

import java.util.Arrays;

public class KMP {

    public static void main(String[] args) {
        KMP kmp = new KMP();
        String s = "ababba";
        int[] nxt = kmp.nxt(s);
        System.out.println(Arrays.toString(nxt));
    }

    public int[] nxt(String s) {
        char[] sCharArray = s.toCharArray();
        int[] nxt = new int[s.length()];
        for (int i = 1, j = 0; i < nxt.length; i++) {
            while (j > 0 && sCharArray[i] != sCharArray[j]) {
                j = nxt[j-1];
            }
            if(sCharArray[i]==sCharArray[j]){
                j++;
            }
            nxt[i]=j;
        }
        return nxt;
    }
}
